import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArraySolution {

    public int removeDuplicates(int[] nums) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[slow] != nums[fast]) {
                nums[++slow] = nums[fast];
            }
            ++fast;
        }
        return slow + 1;
    }

    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
            ++fast;
        }
        return slow;
    }

    public void moveZeroes(int[] nums) {
        int slow = 0, fast = 0;
        while (slow < nums.length) {
            if (fast < nums.length) {
                if (nums[fast] != 0) {
                    nums[slow++] = nums[fast];
                }
                ++fast;
            } else {
                nums[slow++] = 0;
            }
        }

    }

    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[] {left + 1, right + 1};
            } else if (sum > target) {
                --right;
            } else {
                ++left;
            }
        }
        return new int[] {-1, -1};
    }

    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }


    String getPalindrome(String str, int left, int right) {
        while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
            --left;
            ++right;
        }
        return str.substring(left + 1, right);
    }

    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); ++i) {
            String lStr = getPalindrome(s, i , i);
            String rStr = getPalindrome(s, i , i + 1);
            res = lStr.length() > res.length() ? lStr : res;
            res = rStr.length() > res.length() ? rStr : res;
        }
        return res;
    }

    public static void main(String[] args) {
        ArraySolution solution = new ArraySolution();
        // solution.reverseString("abcdefg".toCharArray());
        solution.longestPalindrome("babad");
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        for (int[] booking : bookings) {
            diffIncrease(diff, booking);
        }
        return diffResult(diff);
    }

    private int[] diffResult(int[] diff) {
        int[] result = new int[diff.length];
        result[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }

    private void diffIncrease(int[] diff, int[] booking) {
        diff[booking[0] - 1] += booking[2];
        if (booking[1] < diff.length) {
            diff[booking[1]] -= booking[2];
        }
    }

    public boolean carPooling(int[][] trips, int capacity) {
        int toMax = 0;
        for (int[] trip : trips) {
            toMax = Math.max(toMax, trip[2]);
        }
        int length = toMax + 1;
        int[] diff = new int[length];
        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            diff[trip[2]] -= trip[0];
        }

        int people = 0;
        for (int i = 0; i < length; i++) {
            people += diff[i];
            if (people > capacity) {
                return false;
            }
        }
        return true;
    }


    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int leftBound = 0, upperBound = 0, rightBound = n - 1, bottomBound = m - 1;
        int count = m * n;
        List<Integer> list = new ArrayList<>(count);
        while (list.size() < count) {
            if (upperBound <= bottomBound) {
                for (int i = leftBound; i <= rightBound; i++) {
                    list.add(matrix[upperBound][i]);
                }
                ++upperBound;
            }
            if (leftBound <= rightBound) {
                for (int i = upperBound; i <= bottomBound; i++) {
                    list.add(matrix[i][rightBound]);
                }
                --rightBound;
            }
            if (upperBound <= bottomBound) {
                for (int i = rightBound; i >= leftBound; --i) {
                    list.add(matrix[bottomBound][i]);
                }
                --bottomBound;
            }
            if (leftBound <= rightBound) {
                for (int i = bottomBound; i >= upperBound; i--) {
                    list.add(matrix[i][leftBound]);
                }
                ++leftBound;
            }
        }
        return list;
    }
}

class NumArray {
    private int[] preSums;

    public NumArray(int[] nums) {
        this.preSums = new int[nums.length + 1];
        preSums[0] = 0;
        for (int i = 1; i <= nums.length; ++i) {
            preSums[i] = preSums[i - 1] + nums[i - 1];
        }
    }

    public int sumRange(int left, int right) {
        return this.preSums[right + 1] - this.preSums[left];
    }
}

class NumMatrix {
    private int[][] presSums;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        presSums = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                presSums[i][j] = presSums[i - 1][j] + presSums[i][j - 1] - presSums[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return presSums[row2 + 1][col2 + 1] - presSums[row2 + 1][col1] - presSums[row1][col2 + 1] + presSums[row1][col1];
    }
}

